/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package cs;

/**
 *
 * @author QuangHieu
 */
import java.util.Scanner;

/**
 *
 * @author QuangHieu
 */
class TNodeT {

    int data;
    int count;
    TNodeT left, right;

    TNodeT(int x) {
        data = x;
        count = 1;
        left = right = null;
    }

    TNodeT(int x, TNodeT l, TNodeT r) {
        data = x;
        count = 1;
        left = l;
        right = r;
    }

    TNodeT() {
    }
}

class MyTreeTrung {

    TNodeT root;

    MyTreeTrung() {
        root = null;
    }

    //chen
    private TNodeT insert(TNodeT r, int x) {
        if (r == null) {
            return new TNodeT(x);
        } else if (x > r.data) {
            r.right = insert(r.right, x);
            return r;
        }
        if (x < r.data) {
            r.left = insert(r.left, x);
            return r;
        }
        r.count++;
        return r;
    }

    void insert(int x) {
        root = insert(root, x);
    }

    //tao cay
    private void taoCay() {
        root = null;
        int x;
        Scanner kb = new Scanner(System.in);
        while (true) {
            System.out.print("\nNhap x de chen vao cay(nhap 0 de dung):");
            x = kb.nextInt();
            if (x == 0) {
                break;
            }
            insert(x);
        }
    }

    // duyet trung tu
    private void duyetTrungTu(TNodeT t) {
        if (t != null) {
            duyetTrungTu(t.left);
            while (t.count > 0) {
                System.out.print(" " + t.data);
                t.count--;
            }
            duyetTrungTu(t.right);
        }
    }

    void duyetTrungTu() {
        duyetTrungTu(root);
    }

    //tim va xoa
    private TNodeT xoa(TNodeT r, int x) {
        if (r == null) {
            System.out.print("Khong ton tai!");
            return null;
        }
        if (x < r.data) {
            r.left=xoa(r.left,x);
            return r;
        }
        if (x > r.data) {
            r.right= xoa(r.right, x);
            return r;
        } else {
            if (r.count > 1) {
                r.count--;
                return r;
            } else {
                if ((r.left == null) && (r.right == null))
                    return null;
                    else if (r.left == null) 
                        return r.right;
                        else if (r.right == null) 
                            return r.left;
                            else {
                                TNodeT p=r.left;
                                while(p.right!=null) p=p.right;
                                r.data=p.data; 
                                r.count=p.count;
                                p.count=1;
                                r.left=xoa(r.left,p.data);
                                return r;
                            }
            }
        }
    }

    void xoa(int x){
        root=xoa(root,x);
    }

    public static void main(String args[]) {
        MyTreeTrung mt = new MyTreeTrung();
        mt.taoCay();
        mt.insert(10);
        mt.duyetTrungTu();
        mt.xoa(5);
        System.out.println();
    }
}
